package pacman.entries.pacman.meta_graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import pacman.game.Game;
import pacman.game.Constants.MOVE;
import pacman.game.internal.Maze;
import pacman.game.internal.Node;

public class MetaGraph {

	private static MetaGraph s_CurrentGraph = null;
	public static MetaGraph currentGraph() { return s_CurrentGraph; }
	
	public MetaGraph(Game game, MetaGraphEvaluator evaluator) {
		BuildStructure(game);
		m_Evaluator = evaluator;
		s_CurrentGraph = this;
	}
	
	public MetaGraphPath bestPath(Game game) {
		UpdateEdgePillCounts(game);
		return choosePath(game);
	}

	// _______________________________________________ EVALUATION
	
	MetaGraphEvaluator m_Evaluator;
	
	public void UpdateEdgePillCounts(Game game) {
		if (!game.pillWasEaten)
			return;
		
		MetaGraphEdge edge = getEdgeFromGraphNode(game.getPacmanCurrentNodeIndex());
		if (edge != null)
			edge.decrementPillCount();
	}
	
	// _______________________________________________ DECISIONS
	
	private MetaGraphPath choosePath(Game game) {
		
		int index = game.getPacmanCurrentNodeIndex();
		
		// for each path, score that path and take the best
		Collection<MetaGraphPath> allPaths = allPathsWithIndexAndLength(index, 3);
		float bestScore = Float.MIN_VALUE;
		boolean hasSet = false;
		
		MetaGraphPath bestPath = null;
		for (MetaGraphPath path : allPaths) {
			float score = path.calcScore(game, m_Evaluator);
			if (!hasSet || score > bestScore) {
				bestScore = score;
				bestPath = path;
				hasSet = true;
			}
		}
		
		return bestPath;
	}
	
	public Collection<MetaGraphPath> allPathsWithIndexAndLength(int index, int length) {
		
		List<MetaGraphPath> pathList = new LinkedList<MetaGraphPath>();
		
		MetaGraphNode node = getNodeFromGraphNode(index);
		if (node != null) { // if pacman is at a meta-node, start with the path consisting of that metanode
			pathList.add(new MetaGraphPath(node));
		}
		else { // else start with the paths going to each side of the current edge
			MetaGraphEdge edge = getEdgeFromGraphNode(index);
			if (edge == null) {
//				throw new NullPointerException("No edge found for current index: " + index);
				return pathList;
			}
			pathList.add(new MetaGraphPath(edge.getNode1()));
			pathList.add(new MetaGraphPath(edge.getNode2()));
		}
		
		// TODO: extend starting paths to paths of length to consider
		Collection<MetaGraphPath> recentPaths = new LinkedList<MetaGraphPath>(pathList);
		for (int i = 0; i < length; i++) {
			Collection<MetaGraphPath> newPaths = new LinkedList<MetaGraphPath>();
			for (MetaGraphPath path : recentPaths)
				newPaths.addAll(path.PathsOfNextLength());
			pathList.addAll(newPaths);
			recentPaths = newPaths;
		}
		
		return pathList;
	}
	
	// _______________________________________________ STRUCTURE

	private HashMap<Integer,MetaGraphNode> m_Nodes = new HashMap<Integer,MetaGraphNode>();
	private HashSet<MetaGraphEdge> m_Edges = new HashSet<MetaGraphEdge>();
	// for every non-meta node in the maze, associate the two meta nodes that surround it
	// the hash map associates each meta-node with a direction from the given node
	private HashMap<Integer, HashMap<MOVE, MetaGraphNode>> m_NearestMetaNodes = new HashMap<Integer, HashMap<MOVE, MetaGraphNode>>();   
	
	public MetaGraphNode getNodeFromGraphNode(int index) {
		
		Integer key = new Integer(index);
		
		if (!m_Nodes.containsKey(key))
			return null;
		
		return m_Nodes.get(key);
	}
	
	public MetaGraphEdge getEdgeFromGraphNode(int index) {
		
		Integer key = new Integer(index);
		
		if(!m_NearestMetaNodes.containsKey(key))
			return null;
		
		HashMap<MOVE, MetaGraphNode> map = m_NearestMetaNodes.get(key);
		Iterator<MetaGraphNode> iter = map.values().iterator();
		
		if (map.size() < 2) {
			//System.out.println("Edge for graph index " + index + " has less than two nodes.");
			return null;
		}
		
		return getEdgeBetweenMetaNodes(iter.next(), iter.next());
	}
	
	public Iterator<MetaGraphNode> getMetaNodeIterator() {
		return m_Nodes.values().iterator();
	}
	
	public Iterator<MetaGraphEdge> getMetaEdgeIterator() {
		return m_Edges.iterator();
	}
	
	// returns null if no such edge exists
	public MetaGraphEdge getEdgeBetweenMetaNodes(MetaGraphNode node1, MetaGraphNode node2) {
		return node1.getEdgeBetween(node2);
	}
	
	public int getPillCountBetweenMetaNodes(MetaGraphNode node1, MetaGraphNode node2) {
		return getEdgeBetweenMetaNodes(node1, node2).getPillCount();
	}
	
	// eat a pill at the given graph node index
	// this decrements the pill count on the edge that the node is in
	public int eatPillAtNodeIndex(int index) {
		return getEdgeFromGraphNode(index).decrementPillCount();
	}
	
	private void BuildStructure(Game game) {
		FindMetaNodes(game);
		FindMetaEdges(game);
	}
	
	// populates m_Nodes
	private void FindMetaNodes(Game game) {
		for(int index : game.getJunctionIndices()) {
			m_Nodes.put(index, new MetaGraphNode(index));
		}
		for(int index : game.getPowerPillIndices()) {
			m_Nodes.put(index, new MetaGraphNode(index));
		}
	}
	
	// checks the stores meta-nodes for the given graph node
	public boolean IsMetaNode(int nodeIndex) {
		return m_Nodes.containsKey(nodeIndex);
	}
	
	// populates m_Edges and m_NearestMetaNodes
	// only call after m_Nodes has been populated
	private void FindMetaEdges(Game game) {
		MetaGraphNode start = ((MetaGraphNode[])m_Nodes.values().toArray(new MetaGraphNode[0]))[0];
		FindMetaEdges(start, game);
	}
	private void FindMetaEdges(MetaGraphNode mnode, Game game) {
		mnode.found = true;
		Maze maze = game.getCurrentMaze();
		int currentIndex = mnode.getIndex();
		Node currentNode = maze.graph[currentIndex];
		for(MOVE move : new MOVE[]{MOVE.UP, MOVE.DOWN, MOVE.LEFT, MOVE.RIGHT}) {
			if(mnode.getAdjacentMetaNode(move) != null) {
				continue;  // this edge has already been traversed
			}
			
			int next = game.getNeighbour(currentIndex, move);
			if(next < 0) {
				continue;    // there is no edge in this direction
			}
			MOVE nextMove;
			int previous = currentIndex;
			MOVE previousMove = game.getMoveToMakeToReachDirectNeighbour(next, previous);
			
			ArrayList<Integer> intermediates = new ArrayList<Integer>(100);
			// stores the move towards the next corner, and towards the previous corner, for each node.
			// first move is towards the previous corner, second move is towards the next corner
			ArrayList<MOVE[]> intermediateMoves = new ArrayList<MOVE[]>(100); 
			
			// look for the next meta node
			// count all the pills along the way
			// pill count should include the end points of the edge!
			int pillCount = 0;
			if(game.getPillIndex(currentIndex) > -1) pillCount++;
			while(!m_Nodes.containsKey(next)) {
				intermediates.add(next);
				int pillIndex = game.getPillIndex(next);
				if(pillIndex > -1) pillCount++;    // add to pill count if this node is a pill
				// for(int adjacentNode : maze.graph[next].neighbourhood.values() ) {
				for(Entry<MOVE, Integer> adjacentNode : maze.graph[next].neighbourhood.entrySet() ) {
					// assume that the nodes are not junctions (they should all have been added to m_CornerIndexes)
					int adjacentNodeIndex = adjacentNode.getValue();
					nextMove = adjacentNode.getKey();
					if(previous != adjacentNodeIndex) {
						previous = next;
						next = adjacentNodeIndex;
						intermediateMoves.add(new MOVE[]{previousMove, nextMove});
						break;
					}
				}
			}
			
			// now the next meta node has been reached.  it is stored in "next"
			int nextMetaNodeIndex = next;
			MetaGraphNode nextMetaNode = m_Nodes.get(nextMetaNodeIndex);
			if(game.getPillIndex(nextMetaNodeIndex) > -1) pillCount++;
			// the move that goes from the next meta node the the current meta node
			MOVE oppositeMove = game.getMoveToMakeToReachDirectNeighbour(nextMetaNodeIndex, previous);
			MetaGraphEdge edge = MetaGraphNode.CreateEdgeBetween(mnode, move, nextMetaNode, oppositeMove);
			
			// add the new edge to the metagraph
			m_Edges.add(edge);
			
			// set the pill count on the edge between the nodes
			edge.setPillCount(pillCount);
			
			// add all the intermediate nodes to the m_NearestCorners map
			Iterator<MOVE[]> moveIterator = intermediateMoves.iterator();
			Iterator<Integer> indexIterator = intermediates.iterator();
			while(moveIterator.hasNext() && indexIterator.hasNext()) {
				int intermediate = indexIterator.next();
				MOVE[] moves = moveIterator.next();
				HashMap<MOVE, MetaGraphNode> movemap = new HashMap<MOVE, MetaGraphNode>();
				movemap.put(moves[0], mnode);
				movemap.put(moves[1], nextMetaNode);
				// m_NearestCorners.put(intermediate, new CornerNode[]{corner, nextCornerNode});
				m_NearestMetaNodes.put(intermediate, movemap);
			}
			
			// continue traversing the corners
			if(!nextMetaNode.found) {
				FindMetaEdges(nextMetaNode, game); 
			}
		}
	}
}
